package com.hch.datastructure.lru;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

/**
 * @author HeCongHui
 * @date 2022/6/24 09:40
 */
public class LrfCache {

    /**
     * key到val的映射
     */

    Map<Integer, Integer> keyToVal;

    /**
     * key到freq（使用频次）的映射
     */

    Map<Integer, Integer> keyToFreq;

    /**
     * freq到key的映射，一对多的关系，运用LinkedHashSet的数据结构方便对key值的集合进行管理，
     * 链表机构按时序排序，hash结构，能快速找相应的key值
     */

    Map<Integer, LinkedHashSet<Integer>> freqToKeys;

    /**
     * 记录最小使用频次
     */
    int miniFreq;

    /**
     * 最大容量
     */
    int cap;

    /**
     * 初始化
     *
     * @param capacity
     */
    public LrfCache(int capacity) {
        this.keyToVal = new HashMap<>();
        this.keyToFreq = new HashMap<>();
        this.freqToKeys = new HashMap<>();
        this.cap = capacity;
        this.miniFreq = 0;
    }

    /**
     * 通过key得到val，相当于实际从缓存中点开某个页面
     *
     * @param key
     * @return
     */
    public int get(int key) {
        if (!this.keyToVal.containsKey(key)) {
            return -1;
        }
        //增加一次使用频率,算法核心之一
        increaseFreq(key);
        return this.keyToVal.get(key);
    }

    public void put(int key, int val) {
        // 没有容量直接返回
        if (this.cap <= 0) {
            return;
        }
        // 如果key值已经存在，覆盖相应的val
        if (this.keyToVal.containsKey(key)) {
            this.keyToVal.put(key, val);
            //增加一次使用频率,算法核心之一
            increaseFreq(key);
            return;
        }
        // 如果key不存在需要插入
        // 如果容量已满，需要删除使用频次最小的key
        if (this.keyToVal.size() >= this.cap) {

            removeMiniFreq();
        }
        //插入对应的key，val，freq为1
        this.keyToVal.put(key, val);
        this.keyToFreq.put(key, 1);
        //如果使用频率1对应的集合为空则初始化LinkedHashSet
        this.freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
        //将该key值放入到LinkedHashSet集合里
        this.freqToKeys.get(1).add(key);
        this.miniFreq = 1;
    }

    /**
     * 去除最少使用频率的key
     */
    private void removeMiniFreq() {
        //得到最少使用频率的key值集合
        LinkedHashSet<Integer> keys = this.freqToKeys.get(this.miniFreq);
        //在集合中找到最先插入的值就可以了
        Integer deleteKey = keys.iterator().next();
        //更新fk表
        //现将要删除的key值从LinkedHashSet集合里删除
        keys.remove(deleteKey);
        if (keys.isEmpty()) {
            //如果this.miniFreq(key)相对应的LinkedHashSet集合为空则删除掉相应值
            this.freqToKeys.remove(this.miniFreq);
        }
        //更新kf表
        this.keyToFreq.remove(deleteKey);
        //更新kv表
        this.keyToVal.remove(deleteKey);


    }

    /**
     * 增加key的使用频次
     *
     * @param key
     */
    private void increaseFreq(int key) {
        //得到相应key值的使用频率
        Integer freq = keyToFreq.get(key);
        //更新kf
        keyToFreq.put(key, freq + 1);
        //更新fk表 将key从freq对应的LinkedHashSet列表中删除
        LinkedHashSet<Integer> keyList = this.freqToKeys.get(freq);
        keyList.remove(key);
        //将key加入到freq+1对应的LinkedHashSet列表中
        this.freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
        this.freqToKeys.get(freq + 1).add(key);
        //如果freq对应的列表空了，移除这个freq
        if (this.freqToKeys.get(freq).isEmpty()) {
            this.freqToKeys.remove(freq);
            if (freq == this.miniFreq) {
                this.miniFreq++;
            }
        }


    }
}
